﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Diagnostics;

namespace Mogre_Procedural.std
{

   // public class vector<T> : List<T> { 
//<p>c.back()传回最后一个数据，不检查这个数据是否存在。</p>
//<p>c.clear() 移除容器中所有数据。</p>
//<p>c.empty()判断容器是否为空。</p>
//<p>c.front() 传回地一个数据。</p>
//<p>c.pop_back() 删除最后一个数据。</p>
//<p>c.push_back(elem) 在尾部加入一个数据。</p>
        
    //}
//<h1>列表(list)</h1>
//<p>由节点组成的双向链表，每个结点包含着一个元素</p>
    /// <summary>
    ///		Map class, a little different from the Axiom.Collections.Map class
    /// </summary>
    /// <remarks>
    ///     A map allows multiple values per key, unlike the Hashtable which only allows
    ///     unique keys and only a single value per key.  Multiple values assigned to the same
    ///     key are placed in a "bucket", which in this case is an ArrayList.
    ///     <p/>
    ///     An example of values in a map would look like this:
    ///     Key     Value
    ///     "a"     "Alan"
    ///     "a"     "Adam"
    ///     "b"     "Brien"
    ///     "c"     "Chris"
    ///     "c"     "Carl"
    ///     etc
    ///     <p/>
    ///     Currently, enumeration is the only way to iterate through the values, which is
    ///     more pratical in terms of how the Map works internally anyway.  Intial testing showed
    ///     that inserting and iterating through 100,000 items, the Inserts took ~260ms and a full
    ///     enumeration of them all (with unboxing of the value type stored in the map) took between 16-30ms.
    /// </remarks>
    public class Map
    {
        #region Fields

        /// <summary>
        ///     Number of total items currently in this map.
        /// </summary>
        protected int count;

        /// <summary>
        ///     A list of buckets.
        /// </summary>
        public Hashtable buckets;

        #endregion Fields

        #region Constructor

        /// <summary>
        ///     Default constructor.
        /// </summary>
        public Map() {
            this.buckets = new Hashtable();
        }

        #endregion Constructor

        /// <summary>
        ///     Clears this map of all contained objects.
        /// </summary>
        public void Clear() {
            this.buckets.Clear();
            this.count = 0;
        }

        /// <summary>
        ///     Clears the bucket with given key.
        /// </summary>
        public void Clear(object key) {
            var bucket = (ArrayList)this.buckets[key];
            if (bucket != null) {
                this.count -= bucket.Count;
                this.buckets.Remove(key);
            }
        }

        /// <summary>
        ///     Given a key, Find will return an IEnumerator that allows
        ///     you to iterate over all items in the bucket associated
        ///     with the key.
        /// </summary>
        /// <param name="key">Key for look for.</param>
        /// <returns>IEnumerator to go through the items assigned to the key.</returns>
        public IEnumerator Find(object key) {
            if (this.buckets[key] == null) {
                return null;
            }
            else {
                return ((ArrayList)this.buckets[key]).GetEnumerator();
            }
        }

        public IList FindBucket(object key) {
            if (this.buckets[key] == null) {
                return null;
            }
            else {
                return (ArrayList)this.buckets[key];
            }
        }

        /// <summary>
        ///     Given a key, FindFirst will return the first item in the bucket
        ///     associated with the key.
        /// </summary>
        /// <param name="key">Key to look for.</param>
        public object FindFirst(object key) {
            if (this.buckets[key] == null) {
                return null;
            }
            else {
                return ((ArrayList)this.buckets[key])[0];
            }
        }

        /// <summary>
        ///     Gets the count of objects mapped to the specified key.
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public int Count(object key) {
            if (this.buckets[key] != null) {
                return ((ArrayList)this.buckets[key]).Count;
            }

            return 0;
        }

        /// <summary>
        ///     Inserts a value into a bucket that is specified by the
        ///     key.
        /// </summary>
        /// <param name="key"></param>
        /// <param name="val"></param>
        public void Insert(object key, object val) {
            ArrayList container = null;

            if (this.buckets[key] == null) {
                container = new ArrayList();
                this.buckets.Add(key, container);
            }
            else {
                container = (ArrayList)this.buckets[key];
            }

            // TODO: Doing the contains check is extremely slow, so for now duplicate items are allowed
            //if(!container.Contains(val)) {
            container.Add(val);
            this.count++;
            //}
        }

        /// <summary>
        ///     Gets the total count of all items contained within the map.
        /// </summary>
        public int TotalCount {
            get {
                return this.count;
            }
        }

        /// <summary>
        ///     Gets an appropriate enumerator for the map, customized to go
        ///     through each key in the map and return a Pair of the key and
        ///     an ArrayList of the values associated with it.
        /// </summary>
        /// <returns></returns>
        public IEnumerator GetBucketEnumerator() {
            return this.buckets.Keys.GetEnumerator();
        }
    }

    /// <summary>
    ///     The MultiMap is a C# conversion of the std::buckets container from the C++ 
    ///     standard library.  
    /// </summary>
    /// <remarks>
    ///     A buckets allows multiple values per key, unlike IDictionary<TKey, TValue> which only allows
    ///     unique keys and only a single value per key.  Multiple values assigned to the same
    ///     key are placed in a "bucket", which in this case is a List<TValue>.
    ///     <p/>
    ///     An example of values in a buckets would look like this:
    ///     Key     Value
    ///     "a"     "Alan"
    ///     "a"     "Adam"
    ///     "b"     "Brien"
    ///     "c"     "Chris"
    ///     "c"     "Carl"
    ///     etc
    ///     <p/>
    ///     Currently, enumeration is the only way to iterate through the values, which is
    ///     more pratical in terms of how the MultiMap works internally anyway.  Intial testing showed
    ///     that inserting and iterating through 100,000 items, the Inserts took ~260ms and a full
    ///     enumeration of them all (with unboxing of the value type stored in the buckets) took between 16-30ms.
    /// </remarks>
    public class MultiMap<TKey, TValue>
        : IDictionary, IDictionary<TKey, List<TValue>>, IEnumerable<TValue>, IEnumerable<List<TValue>>
    {
        #region Fields

        private readonly Dictionary<TKey, List<TValue>> buckets;

        /// <summary>
        ///     Number of total items currently in this buckets.
        /// </summary>
        private int count;

        #endregion

        #region Constructors

        /// <summary>
        ///     Default constructor.
        /// </summary>
        public MultiMap() {
            this.buckets = new Dictionary<TKey, List<TValue>>();
        }

        public MultiMap(IEqualityComparer<TKey> comparer) {
            this.buckets = new Dictionary<TKey, List<TValue>>(comparer);
        }

        #endregion

        #region Instance Properties

        public int Count {
            get {
                return this.buckets.Count;
            }
        }

        /// <summary>
        ///		Gets the number of keys in this map.
        /// </summary>
        public int KeyCount {
            get {
                return this.buckets.Count;
            }
        }

        public int TotalCount {
            get {
                return this.count;
            }
        }

        #endregion

        #region Instance Methods

        /// <summary>
        ///     Inserts a value into a bucket that is specified by the
        ///     key.
        /// </summary>
        /// <param name="key"></param>
        /// <param name="val"></param>
        public void Add(TKey key, TValue value) {
            List<TValue> container;

            if (!this.buckets.ContainsKey(key)) {
                container = new List<TValue>();
                this.buckets.Add(key, container);
            }
            else {
                container = this.buckets[key];
            }

            // TODO: Doing the contains check is extremely slow, so for now duplicate items are allowed
            //if (!container.Contains(value))
            //{
            container.Add(value);
            this.count++;
            //}
        }

        /// <summary>
        ///     Gets the count of objects mapped to the specified key.
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public int BucketCount(TKey key) {
            if (this.buckets.ContainsKey(key)) {
                return this.buckets[key].Count;
            }

            return 0;
        }

        public void Clear() {
            this.buckets.Clear();
            this.count = 0;
        }

        public void Clear(TKey key) {
            if (this.buckets.ContainsKey(key)) {
                this.count -= this.buckets[key].Count;
            }
            this.buckets[key].Clear();
        }

        /// <summary>
        ///     Given a key, Find will return an IEnumerator that allows
        ///     you to iterate over all items in the bucket associated
        ///     with the key.
        /// </summary>
        /// <param name="key">Key for look for.</param>
        /// <returns>IEnumerator to go through the items assigned to the key.</returns>
        public IEnumerator<TValue> Find(TKey key) {
            if (this.buckets.ContainsKey(key)) {
                return this.buckets[key].GetEnumerator();
                //int length = buckets[key].Count;
                //IList<TValue> bucket = buckets[key];
                //for (int i = 0; i < length; i++)
                //{
                //    yield return bucket[i];
                //}
            }
            return null;
        }

        public List<TValue> FindBucket(TKey key) {
            if (!this.buckets.ContainsKey(key)) {
                return null;
            }
            return this.buckets[key];
        }

        /// <summary>
        ///     Given a key, FindFirst will return the first item in the bucket
        ///     associated with the key.
        /// </summary>
        /// <param name="key">Key to look for.</param>
        public object FindFirst(TKey key) {
            if (!this.buckets.ContainsKey(key)) {
                return null;
            }
            else {
                return (this.buckets[key])[0];
            }
        }

        public IEnumerator<KeyValuePair<TKey, List<TValue>>> GetBucketsEnumerator() {
            foreach (var item in this.buckets) {
                yield return item;
            }
        }

        private void Add(TKey key, IList<TValue> value) {
            List<TValue> container;

            if (!this.buckets.ContainsKey(key)) {
                container = new List<TValue>();
                this.buckets.Add(key, container);
            }
            else {
                container = this.buckets[key];
            }

            foreach (TValue i in value) {
                // TODO: Doing the contains check is extremely slow, so for now duplicate items are allowed
                if (!container.Contains(i)) {
                    container.Add(i);
                    this.count++;
                }
            }
        }

        #endregion

        #region IDictionary Members

        void IDictionary.Add(object key, object value) {
            if (key is TKey & value is IList<TValue>) {
                Add((TKey)key, (IList<TValue>)value);
            }
        }

        void IDictionary.Clear() {
            Clear();
        }

        bool IDictionary.Contains(object key) {
            if (key is TKey) {
                return ContainsKey((TKey)key);
            }
            return false;
        }

        IDictionaryEnumerator IDictionary.GetEnumerator() {
            throw new NotImplementedException();
        }

        bool IDictionary.IsFixedSize {
            get {
                return (this.buckets as IDictionary).IsFixedSize;
            }
        }

        bool IDictionary.IsReadOnly {
            get {
                return (this.buckets as IDictionary).IsReadOnly;
            }
        }

        ICollection IDictionary.Keys {
            get {
                return this.buckets.Keys;
            }
        }

        void IDictionary.Remove(object key) {
            if (key is TKey) {
                Remove((TKey)key);
            }
        }

        ICollection IDictionary.Values {
            get {
                return this.buckets.Values;
            }
        }

        object IDictionary.this[object key] {
            get {
                if (key is TKey) {
                    return this[(TKey)key];
                }
                return null;
            }
            set {
                if (value is IList<TValue>) {
                    this[(TKey)key] = (List<TValue>)value;
                }
                else {
                    throw new ArgumentException("The key must be of type " + typeof(List<TValue>).ToString(), "value");
                }
            }
        }

        void ICollection.CopyTo(Array array, int index) {
            throw new NotImplementedException();
        }

        int ICollection.Count {
            get {
                return this.count;
            }
        }

        bool ICollection.IsSynchronized {
            get {
                return (this.buckets as ICollection).IsSynchronized;
            }
        }

        object ICollection.SyncRoot {
            get {
                return (this.buckets as ICollection).SyncRoot;
            }
        }

        #endregion

        #region IDictionary<TKey,List<TValue>> Members

        void IDictionary<TKey, List<TValue>>.Add(TKey key, List<TValue> value) {
            Add(key, value);
        }

        public bool ContainsKey(TKey key) {
            return this.buckets.ContainsKey(key);
        }

        public ICollection<TKey> Keys {
            get {
                return this.buckets.Keys;
            }
        }

        public bool Remove(TKey key) {
            bool removed = this.buckets.Remove(key);
            if (removed) {
                this.count--;
                return true;
            }
            return false;
        }

        public bool TryGetValue(TKey key, out List<TValue> value) {
            List<TValue> tvalue;
            this.buckets.TryGetValue(key, out tvalue);
            value = tvalue;
            if (tvalue == null) {
                return false;
            }
            return true;
        }

        public ICollection<List<TValue>> Values {
            get {
                return this.buckets.Values;
            }
        }

        public List<TValue> this[TKey key] {
            get {
                return this.buckets[key];
            }
            set {
                this.buckets[key] = value;
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        void ICollection<KeyValuePair<TKey, List<TValue>>>.Add(KeyValuePair<TKey, List<TValue>> item) {
            Add(item.Key, item.Value);
        }

        void ICollection<KeyValuePair<TKey, List<TValue>>>.Clear() {
            Clear();
        }

        bool ICollection<KeyValuePair<TKey, List<TValue>>>.Contains(KeyValuePair<TKey, List<TValue>> item) {
            return this.buckets.ContainsKey(item.Key);
        }

        void ICollection<KeyValuePair<TKey, List<TValue>>>.CopyTo(KeyValuePair<TKey, List<TValue>>[] array, int arrayIndex) {
            throw new NotImplementedException();
        }

        int ICollection<KeyValuePair<TKey, List<TValue>>>.Count {
            get {
                return Count;
            }
        }

        bool ICollection<KeyValuePair<TKey, List<TValue>>>.IsReadOnly {
            get {
                return (this.buckets as IDictionary).IsReadOnly;
            }
        }

        bool ICollection<KeyValuePair<TKey, List<TValue>>>.Remove(KeyValuePair<TKey, List<TValue>> item) {
            return Remove(item.Key);
        }

        IEnumerator<KeyValuePair<TKey, List<TValue>>> IEnumerable<KeyValuePair<TKey, List<TValue>>>.GetEnumerator() {
            return this.buckets.GetEnumerator();
        }

        #endregion

        #region IEnumerable<List<TValue>> Members

        IEnumerator<List<TValue>> IEnumerable<List<TValue>>.GetEnumerator() {
            foreach (var item in this.buckets) {
                yield return item.Value;
            }
        }

        #endregion

        #region IEnumerable<TValue> Members

        public IEnumerator<TValue> GetEnumerator() {
            foreach (IList<TValue> item in this.buckets.Values) {
                int length = item.Count;
                for (int i = 0; i < length; i++) {
                    yield return item[i];
                }
            }
        }

        #endregion
    }

    /// <summary>
    /// A double-ended queue. Provides fast insertion and removal from
    /// the head or tail end,
    /// and fast indexed access.
    /// </summary>
    /// <typeparam name="T">The type of item to store in the deque.</typeparam>
    public class Deque<T> : ICollection<T>
    {
        #region Constants

        private const int MIN_CAPACITY = 4;

        #endregion Constants

        #region Fields

        private int _capacity = MIN_CAPACITY;
        private int _count;
        private T[] _data;
        private int _head = 0;
        private int _tail = 0;

        #endregion Fields

        #region Constructors

        /// <summary>
        /// Creates a new deque.
        /// </summary>
        public Deque() {
            this._data = new T[this._capacity];
        }

        /// <summary>
        /// Creates a new deque.
        /// </summary>
        /// <param name="capacity">The initial capacity to give the
        ///deque.</param>
        public Deque(int capacity)
            : this() {
            this._capacity = capacity;
        }

        /// <summary>
        /// Creates a new deque from a collection.
        /// </summary>
        /// <param name="collection">A collection of items of type T.</param>
        public Deque(ICollection<T> collection)
            : this() {
            Capacity = collection.Count;
            foreach (var item in collection) {
                Add(item);
            }
        }

        #endregion Constructors

        #region Instance Properties

        /// <summary>
        /// Gets or sets the capacity of the deque. If the count exceeds the
        /// capacity, the capacity will be automatically increased.
        /// </summary>
        public int Capacity {
            get {
                return this._capacity;
            }
            set {
                var previousCapacity = this._capacity;
                this._capacity = System.Math.Max(value, System.Math.Max(this._count, MIN_CAPACITY));
                var temp = new T[this._capacity];
                if (this._tail > this._head) {
                    Array.Copy(this._data, this._head, temp, 0, this._tail + 1 - this._head);
                    this._tail -= this._head;
                    this._head = 0;
                }
                else {
                    Array.Copy(this._data, 0, temp, 0, this._tail + 1);
                    var length = previousCapacity - this._head;
                    Array.Copy(this._data, this._head, temp, this._capacity - length, length);
                    this._head = this._capacity - length;
                }
                this._data = temp;
            }
        }

        #endregion Instance Properties

        #region Instance Indexers

        /// <summary>
        /// Gets the item at the specified position.
        /// </summary>
        /// <param name="position">The position of the item to return.</param>
        /// <returns>An item of type T.</returns>
        public T this[int position] {
            get {
                if (position >= this._count) {
                    throw new ArgumentOutOfRangeException("position");
                }
                return this._data[(this._head + position) % this._capacity];
            }
        }

        #endregion Instance Indexers

        #region Instance Methods

        /// <summary>
        /// Adds an item to the head of the deque.
        /// </summary>
        /// <param name="item">The item to be added.</param>
        public void AddToHead(T item) {
            this._count++;
            if (this._count > this._capacity) {
                Capacity *= 2;
            }
            if (this._count > 1) {
                this._head = Decrement(this._head);
            }
            this._data[this._head] = item;
        }

        /// <summary>
        /// Adds an item to the tail end of the deque.
        /// </summary>
        /// <param name="item">The item to be added.</param>
        public void AddToTail(T item) {
            this._count++;
            if (this._count > this._capacity) {
                Capacity *= 2;
            }
            if (this._count > 1) {
                this._tail = Increment(this._tail);
            }
            this._data[this._tail] = item;
        }

        /// <summary>
        /// Gets the item at the head of the deque.
        /// </summary>
        /// <returns>An item of type T.</returns>
        public T PeekHead() {
            return this._data[this._head];
        }

        /// <summary>
        /// Gets the item at the tail of the deque.
        /// </summary>
        /// <returns>An item of type T.</returns>
        public T PeekTail() {
            return this._data[this._tail];
        }

        /// <summary>
        /// Gets and removes an item at the specified index.
        /// </summary>
        /// <param name="index">The index at which to remove the item.</param>
        /// <returns>An item of type T.</returns>
        public T RemoveAt(int index) {
            if (index >= this._count) {
                throw new ArgumentOutOfRangeException("index");
            }

            this._count--;
            var i = (this._head + index) % this._capacity;
            var item = this._data[i];
            if (i < this._head) {
                Array.Copy(this._data, i + 1, this._data, i, this._tail - i);
                this._data[this._tail] = default(T);
                this._tail = Decrement(this._tail);
            }
            else {
                Array.Copy(this._data, this._head, this._data, this._head + 1, i - this._head);
                this._data[this._head] = default(T);
                this._head = Increment(this._head);
            }
            return item;
        }

        /// <summary>
        /// Removes an item from the head of the deque.
        /// </summary>
        /// <returns>An item of type T.</returns>
        public T RemoveFromHead() {
            this._count--;
            if (this._count < 0) {
                throw new InvalidOperationException("DequeEmptyException");
            }
            var item = this._data[this._head];
            this._data[this._head] = default(T);
            this._head = Increment(this._head);
            return item;
        }

        /// <summary>
        /// Removes an item from the tail of the deque.
        /// </summary>
        /// <returns>An item of type T.</returns>
        public T RemoveFromTail() {
            this._count--;
            if (this._count < 0) {
                throw new InvalidOperationException("DequeEmptyException");
            }
            var item = this._data[this._tail];
            this._data[this._tail] = default(T);
            if (this._count > 1) {
                this._tail = Decrement(this._tail);
            }
            return item;
        }

        /// <summary>
        /// Creates an array of the items in the deque.
        /// </summary>
        /// <returns>An array of type T.</returns>
        public T[] ToArray() {
            var array = new T[this._count];
            CopyTo(array, 0);
            return array;
        }

        /// <summary>
        /// Decrements (and wraps if necessary) an index
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private int Decrement(int index) {
            return (index + this._capacity - 1) % this._capacity;
        }

        /// <summary>
        /// Increments (and wraps if necessary) an index
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private int Increment(int index) {
            return (index + 1) % this._capacity;
        }

        #endregion Instance Methods

        #region ICollection<T> Members

        /// <summary>
        /// Gets the number of items in the deque.
        /// </summary>
        public int Count {
            get {
                return this._count;
            }
        }

        /// <summary>
        /// Copies the deque to an array at the specified index.
        /// </summary>
        /// <param name="array">One dimensional array that is the
        /// destination of the copied elements.</param>
        /// <param name="arrayIndex">The zero-based index at which
        /// copying begins.</param>
        public void CopyTo(T[] array, int arrayIndex) {
            if (this._count == 0) {
                return;
            }
            if (this._head < this._tail) {
                Array.Copy(this._data, this._head, array, arrayIndex, this._tail + 1 - this._head);
            }
            else {
                var headLength = this._capacity - this._head;
                Array.Copy(this._data, this._head, array, arrayIndex, headLength);
                Array.Copy(this._data, 0, array, arrayIndex + headLength, this._tail + 1);
            }
        }

        /// <summary>
        /// Clears all items from the deque.
        /// </summary>
        public void Clear() {
            Array.Clear(this._data, 0, this._capacity);
            this._head = 0;
            this._tail = 0;
            this._count = 0;
        }

        /// <summary>
        /// Gets an enumerator for the deque.
        /// </summary>
        /// <returns>An IEnumerator of type T.</returns>
        public IEnumerator<T> GetEnumerator() {
            for (var i = 0; i < this._count; i++) {
                yield return this[i];
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        /// <summary>
        /// Adds an item to the tail of the deque.
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item) {
            AddToTail(item);
        }

        /// <summary>
        /// Checks to see if the deque contains the specified item.
        /// </summary>
        /// <param name="item">The item to search the deque for.</param>
        /// <returns>A boolean, true if deque contains item.</returns>
        public bool Contains(T item) {
            for (var i = 0; i < Count; i++) {
                if (this[i].Equals(item)) {
                    return true;
                }
            }
            return false;
        }

        /// <summary>
        /// Gets whether or not the deque is readonly.
        /// </summary>
        public bool IsReadOnly {
            get {
                return false;
            }
        }

        /// <summary>
        /// Removes an item from the deque.
        /// </summary>
        /// <param name="item">The item to be removed.</param>
        /// <returns>Boolean true if the item was removed.</returns>
        public bool Remove(T item) {
            for (var i = 0; i < Count; i++) {
                if (this[i].Equals(item)) {
                    RemoveAt(i);
                    return true;
                }
            }
            return false;
        }

        #endregion ICollection<T> Members
    }
    
    
    ///// <summary>
    /////     相当于C++基础库中的std::map
    /////     一个Map也是键/值对的集合但是与哈希表不同的是Map允许一个键对应多个值
    /////     关联到同一个键上的多个值放在一个桶中  
    ///// </summary>
    //public class Map : IEnumerable
    //{
    //    /// <summary>
    //    ///    总项数
    //    /// </summary>
    //    protected int count;

    //    /// <summary>
    //    /// 桶列表
    //    /// </summary>
    //    protected SortedList buckets;

    //    public Map() {
    //        buckets = new SortedList();
    //    }

    //    /// <summary>
    //    /// 用指定比较器进行桶排序
    //    /// </summary>
    //    /// <param name="comparer"></param>
    //    public Map(IComparer comparer) {
    //        buckets = new SortedList(comparer);
    //    }

    //    /// <summary>
    //    ///    清空
    //    /// </summary>
    //    public void Clear() {
    //        buckets.Clear();
    //        count = 0;
    //    }

    //    /// <summary>
    //    /// 根据给定键返回关联的值的枚举器
    //    /// </summary>
    //    /// <param name="key"></param>
    //    /// <returns></returns>
    //    public IEnumerator Find(object key) {
    //        if (buckets[key] == null) {
    //            return null;
    //        }
    //        else {
    //            return ((ArrayList)buckets[key]).GetEnumerator();
    //        }
    //    }

    //    /// <summary>
    //    /// 根据给定键返回关联的值的列表
    //    /// </summary>
    //    /// <param name="key"></param>
    //    /// <returns></returns>
    //    public IList FindBucket(object key) {
    //        if (buckets[key] == null) {
    //            return null;
    //        }
    //        else {
    //            return (ArrayList)buckets[key];
    //        }
    //    }

    //    /// <summary>
    //    ///   获得关联到指定键的值得个数
    //    /// </summary>
    //    /// <param name="key"></param>
    //    /// <returns></returns>
    //    public int Count(object key) {
    //        if (buckets[key] != null) {
    //            return ((ArrayList)buckets[key]).Count;
    //        }

    //        return 0;
    //    }

    //    /// <summary>
    //    ///  插入一个键/值对
    //    /// </summary>
    //    /// <param name="key"></param>
    //    /// <param name="val"></param>
    //    public void Insert(object key, object val) {
    //        ArrayList container = null;

    //        if (buckets[key] == null) {
    //            container = new ArrayList();
    //            buckets.Add(key, container);
    //        }
    //        else {
    //            container = (ArrayList)buckets[key];
    //        }

    //        // TODO: 
    //        //if(!container.Contains(val)) {
    //        container.Add(val);
    //        count++;
    //        //}
    //    }

    //    /// <summary>
    //    ///    获取总项数
    //    /// </summary>
    //    public int TotalCount {
    //        get {
    //            return count;
    //        }
    //    }

    //    public IEnumerator GetEnumerator() {
    //        return new MapEnumerator(this);
    //    }

    //    private class MapEnumerator : IEnumerator
    //    {
    //        int totalPos;

    //        int bucketIndex;

    //        int bucketPos;

    //        ArrayList currentBucket;

    //        Map map;

    //        public MapEnumerator(Map map) {
    //            this.map = map;
    //        }

    //        public void Reset() {
    //            totalPos = 0;
    //            bucketIndex = 0;
    //            bucketPos = 0;
    //        }

    //        public object Current {
    //            get {
    //                object key = map.buckets.GetKey(bucketIndex);
    //                object val = currentBucket[bucketPos];
    //                return new Pair(key, val);
    //            }
    //        }

    //        public bool MoveNext() {
    //            if (map.buckets.Count == 0) {
    //                return false;
    //            }

    //            if ((totalPos + 1) == map.count) {
    //                return false;
    //            }

    //            if (currentBucket != null) {
    //                if (bucketPos == (currentBucket.Count - 1)) {
    //                    currentBucket = (ArrayList)map.buckets.GetByIndex(++bucketIndex);
    //                    bucketPos = 0;
    //                }
    //                else {
    //                    bucketPos++;
    //                }

    //                totalPos++;
    //            }
    //            else {
    //                currentBucket = (ArrayList)map.buckets.GetByIndex(bucketIndex);
    //            }

    //            return true;
    //        }

    //    }
    //}
   
    ///// <summary> 
    ///// 表示一个对 
    ///// </summary> 
    //public class Pair
    //{
    //    public object First;
    //    public object Second;

    //    public Pair(object first, object second) {
    //        this.First = first;
    //        this.Second = second;
    //    }
    //}


    /// <summary>
    /// A data structure that contains multiple values for a each key.
    /// </summary>
    /// <typeparam name="K">The type of key.</typeparam>
    /// <typeparam name="V">The type of value.</typeparam>
    //public class Multimap<K, V> : IEnumerable<KeyValuePair<K, ICollection<V>>>
    //{
    //    private readonly Dictionary<K, ICollection<V>> _items = new Dictionary<K, ICollection<V>>();

    //    /// <summary>
    //    /// Gets the collection of values stored under the specified key.
    //    /// </summary>
    //    /// <param name="key">The key.</param>
    //    public ICollection<V> this[K key] {
    //        get {
    //            Ensure.ArgumentNotNull(key, "key");

    //            if (!_items.ContainsKey(key))
    //                _items[key] = new List<V>();

    //            return _items[key];
    //        }
    //    }

    //    /// <summary>
    //    /// Gets the collection of keys.
    //    /// </summary>
    //    public ICollection<K> Keys {
    //        get { return _items.Keys; }
    //    }

    //    /// <summary>
    //    /// Gets the collection of collections of values.
    //    /// </summary>
    //    public ICollection<ICollection<V>> Values {
    //        get { return _items.Values; }
    //    }

    //    /// <summary>
    //    /// Adds the specified value for the specified key.
    //    /// </summary>
    //    /// <param name="key">The key.</param>
    //    /// <param name="value">The value.</param>
    //    public void Add(K key, V value) {
    //        Ensure.ArgumentNotNull(key, "key");
    //        Ensure.ArgumentNotNull(value, "value");

    //        this[key].Add(value);
    //    }

    //    /// <summary>
    //    /// Removes the specified value for the specified key.
    //    /// </summary>
    //    /// <param name="key">The key.</param>
    //    /// <param name="value">The value.</param>
    //    /// <returns><c>True</c> if such a value existed and was removed; otherwise <c>false</c>.</returns>
    //    public bool Remove(K key, V value) {
    //        Ensure.ArgumentNotNull(key, "key");
    //        Ensure.ArgumentNotNull(value, "value");

    //        if (!_items.ContainsKey(key))
    //            return false;

    //        return _items[key].Remove(value);
    //    }

    //    /// <summary>
    //    /// Removes all values for the specified key.
    //    /// </summary>
    //    /// <param name="key">The key.</param>
    //    /// <returns><c>True</c> if any such values existed; otherwise <c>false</c>.</returns>
    //    public bool RemoveAll(K key) {
    //        Ensure.ArgumentNotNull(key, "key");
    //        return _items.Remove(key);
    //    }

    //    /// <summary>
    //    /// Removes all values.
    //    /// </summary>
    //    public void Clear() {
    //        _items.Clear();
    //    }

    //    /// <summary>
    //    /// Determines whether the multimap contains any values for the specified key.
    //    /// </summary>
    //    /// <param name="key">The key.</param>
    //    /// <returns><c>True</c> if the multimap has one or more values for the specified key; otherwise, <c>false</c>.</returns>
    //    public bool ContainsKey(K key) {
    //        Ensure.ArgumentNotNull(key, "key");
    //        return _items.ContainsKey(key);
    //    }

    //    /// <summary>
    //    /// Determines whether the multimap contains the specified value for the specified key.
    //    /// </summary>
    //    /// <param name="key">The key.</param>
    //    /// <param name="value">The value.</param>
    //    /// <returns><c>True</c> if the multimap contains such a value; otherwise, <c>false</c>.</returns>
    //    public bool ContainsValue(K key, V value) {
    //        Ensure.ArgumentNotNull(key, "key");
    //        Ensure.ArgumentNotNull(value, "value");

    //        return _items.ContainsKey(key) && _items[key].Contains(value);
    //    }

    //    /// <summary>
    //    /// Returns an enumerator that iterates through a the multimap.
    //    /// </summary>
    //    /// <returns>An <see cref="IEnumerator"/> object that can be used to iterate through the multimap.</returns>
    //    public IEnumerator GetEnumerator() {
    //        return _items.GetEnumerator();
    //    }

    //    IEnumerator<KeyValuePair<K, ICollection<V>>> IEnumerable<KeyValuePair<K, ICollection<V>>>.GetEnumerator() {
    //        return _items.GetEnumerator();
    //    }
    //}
    //public class MultiMap<K, V> : Dictionary<K, IList<V>>
    //{
    //    public MultiMap() {
    //    }
    //    public MultiMap(IEnumerable<KeyValuePair<K, V>> collection) {
    //        foreach (var pair in collection) {
    //            Map(pair.Key, pair.Value);
    //        }
    //    }

    //    public void Map(K key, V value) {
    //        IList<V> elementsForKey;
    //        if (!TryGetValue(key, out elementsForKey)) {
    //            elementsForKey = new List<V>();
    //            this[key] = elementsForKey;
    //        }
    //        elementsForKey.Add(value);
    //    }
    //    public void Add(K key, V value) {
    //        Map(key, value);
    //    }
    //}
    
    //internal static class Ensure
    //{
    //    public static void ArgumentNotNull(object argument, string name) {
    //        if (argument == null) throw new ArgumentNullException(name, "Cannot be null");
    //    }

    //    public static void ArgumentNotNullOrEmpty(string argument, string name) {
    //        if (String.IsNullOrEmpty(argument)) throw new ArgumentException("Cannot be null or empty", name);
    //    }
    //}



    // public class ListIterator<T> : IEnumerator<T>, IEquatable<ListIterator<T>>
    //{
    //    // Enumerators are positioned before the first element
    //    // until the first MoveNext() call.
    //    int position = int.MaxValue;
    //    IList<T> list = null;
                
    //    public ListIterator(IList<T> c, int p = -1)
    //    {
    //        list = c;
    //        position = p;
    //    }

    //    public void Dispose()
    //    {

    //    }

    //    public bool MoveNext()
    //    {
    //        position = Math.Min(position + 1, list.Count);
    //        return (position < list.Count);
    //    }

    //    public bool MovePrev()
    //    {
    //        position = Math.Max(position - 1, -1);
    //        return (position >= 0);
    //    }

    //    public void Reset()
    //    {
    //        position = -1;
    //    }

    //    public bool IsEnd
    //    {
    //        get { return position >= list.Count; }
    //    }

    //    public int Position
    //    {
    //        get { return position; }
    //        set { position = value; }
    //    }

    //    object IEnumerator.Current
    //    {
    //        get
    //        {
    //            return list[position];
    //        }
    //    }

    //    public T Current
    //    {
    //        get
    //        {
    //            try
    //            {
    //                return list[position];
    //            }
    //            catch (IndexOutOfRangeException)
    //            {
    //                throw new InvalidOperationException();
    //            }
    //        }
    //    }

    //    public bool Equals(ListIterator<T> other )
    //    {
    //        return list == other.list && (position == other.position || (IsEnd && other.IsEnd));
    //    }

    //    public int Distance( ListIterator<T> it )
    //    {
    //        Debug.Assert( list.Equals(it.list) );
    //        return it.position - position;
    //    }

    //    public ListIterator<T> Advance( int distance )
    //    {
    //        return new ListIterator<T>(list, position + distance);
    //    }

    //}

    //struct Range
    //{
    //    public static KeyValuePair<K,V> MakeKeyValuePair<K,V>( K k, V v )
    //    {
    //        return new KeyValuePair<K, V>(k, v);
    //    }

    //    public static ListIterator<T> Begin<T>( IList<T> list )
    //    {
    //        return new ListIterator<T>(list, 0);
    //    }

    //    public static ListIterator<T> End<T>(IList<T> list)
    //    {
    //        return new ListIterator<T>(list, list.Count);
    //    }

    //    public static ListIterator<T> RBegin<T>(IList<T> list)
    //    {
    //        return new ListIterator<T>(list, list.Count);
    //    }

    //    public static ListIterator<T> REnd<T>(IList<T> list)
    //    {
    //        return new ListIterator<T>(list, -1);
    //    }

    //    public static ListIterator<T> LowerBound<T>(ListIterator<T> first, ListIterator<T> last, T value, IComparer<T> pred)
    //    {
    //        // find first element not before _Val, using _Pred
    //        int distance = first.Distance(last);
    //        Debug.Assert(distance >= 0);

    //        while(0 < distance)
    //        {
    //            // divide and conquer, find half that contains answer
    //            int d2 = distance / 2;
    //            ListIterator<T> mid = first.Advance(d2);//!Advance d2.

    //            if (pred.Compare(mid.Current, value) == -1)
    //            {
    //                first.Position = mid.Position + 1;
    //                distance -= d2 + 1;
    //            }
    //            else
    //                distance = d2;
    //        }
    //        return first;
    //    }

    //    public static ListIterator<T> LowerBound<T>(ListIterator<T> first, ListIterator<T> last, T value) where T : IComparable<T>
    //    {
    //        // find first element not before _Val, using _Pred
    //        int distance = first.Distance(last);
    //        Debug.Assert(distance >= 0);

    //        while (0 < distance)
    //        {
    //            // divide and conquer, find half that contains answer
    //            int d2 = distance / 2;
    //            ListIterator<T> mid = first.Advance(d2);//!Advance d2.

    //            if (mid.Current.CompareTo(value) == -1)
    //            {
    //                first.Position = mid.Position + 1;
    //                distance -= d2 + 1;
    //            }
    //            else
    //                distance = d2;
    //        }
    //        return first;
    //    }
    //}

    //public struct KeyValuePairComparer<K,V> : IComparer<KeyValuePair<K,V>> where K : IComparable<K>
    //{
    //    public int Compare( KeyValuePair<K,V> lhs, KeyValuePair<K,V> rhs )
    //    {
    //        return lhs.Key.CompareTo(rhs.Key);
    //    }
    //}
    
    ///// <summary>
    ///// Summary description for MultiMap.
    ///// </summary>
    //public class MultiMap<Key,Value> where Key : IComparable<Key>
    //{
    //    public MultiMap()
    //    {
    //    }
        
    //    public ListIterator<KeyValuePair<Key, Value>> Begin
    //    {
    //        get { return Range.Begin(list); }
    //    }

    //    public ListIterator<KeyValuePair<Key, Value>> RBegin
    //    {
    //        get { return Range.RBegin(list); }
    //    }

    //    public ListIterator<KeyValuePair<Key, Value>> End
    //    {
    //        get { return Range.End(list); }
    //    }

    //    #region member functions

    //    public int Find(Key k)
    //    {
    //        return list.BinarySearch(new KeyValuePair<Key, Value>(k, default(Value)));
    //    }

    //    public Value this[int key]
    //    {
    //        get
    //        {
    //            return list[key].Value;
    //        }
    //        set
    //        {
    //            list[key] = new KeyValuePair<Key,Value>( list[key].Key, value );
    //        }
    //    }

    //    public void Insert( Key k, Value v )
    //    {
    //        KeyValuePair<Key, Value> kp = Range.MakeKeyValuePair(k, v);
    //        ListIterator<KeyValuePair<Key, Value>> it = Range.LowerBound<KeyValuePair<Key, Value>>
    //            (
    //                Begin
    //              , End
    //              , kp
    //              , new KeyValuePairComparer<Key, Value>()
    //            );

    //        if (it.IsEnd)
    //            list.Add(kp);
    //        else
    //            list.Insert(it.Position, kp);
    //    }

    //    #endregion

    //    #region member variables

    //    private List< KeyValuePair<Key,Value> > list = new List< KeyValuePair<Key,Value> >();

    //    #endregion Member Data
    //}
}
